#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <unistd.h>
//#include <>

#define DEGREE 4
#define ORDER (DEGREE)

typedef double keyType;
typedef struct DBObject{
	keyType key;
	char *value;
}DBObject;

typedef struct BPNode{
	_Bool leaf;

	struct BPNode *prevNode;
	struct BPNode *nextNode;
	struct BPNode *childNode[2*ORDER];

	int numKeys;

//	DBObject object[2*ORDER-1];
	keyType keys[ORDER+1];
	char dataStr[ORDER+1][512];//这里就直接分配内存了，memcpy
}BPNode,*pBPNode;

void buildTree(pBPNode *root);
void insert(pBPNode *tree,keyType key,char *string);
void BPTreeInsertNotFull(BPNode *node,keyType key,char *string);
void BPTreeSplitChild(BPNode *parent,BPNode *node,int index);


int main(int argc,char **argv)
{
	BPNode *bRoot = NULL;
	buildTree(&bRoot);

	exit(0);
}

void buildTree(pBPNode *root)
{
	FILE *pfile = fopen("./assgn_bplus_data.txt","r");
	if(pfile == NULL){
		perror("./assgn_bplus_data.txt");
		exit(1);
	}

	keyType key;
	//char *string;
	//char *dataString;
	char string[128];
	char dataString[512];
	//long count = 0;
	
	while(fscanf(pfile,"%s	%s",string,dataString) != EOF){
		key = atof(string);
		//printf("%f,%s\n",key,dataString);
		insert(root,key,dataString);

	}
	fclose(pfile);
}
void insert(pBPNode *tree,keyType key,char *string)
{
	BPNode *root = *tree;
	if(root == NULL){
		root = (pBPNode)calloc(sizeof(BPNode),1);
		if(!root){
			perror("insert--root");
			exit(1);
		}
		root->leaf = true;
		root->numKeys = 1;
		root->keys[0] = key;
		strcpy(root->dataStr[0],string);
		//strncpy(root->dataStr[0],string,sizeof(root->dataStr[0]));
#ifdef DEBUG_INSERT
		printf("node %f,%s\n",root->keys[0],root->dataStr[0]);
		//pause();
#endif
		*tree = root;
		return;
	}
	if(root->numKeys >= (ORDER)){
		//分配新的节点，然后分离节点
#ifdef DEBUG_INSERT
	for(int i=0;i<root->numKeys;i++){
		printf("key:%f,dataString:%s |%d| ",root->keys[i],root->dataStr[i],i);
	}
	printf("\n");
#endif
		BPNode *newParent = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newParent){
			perror("insert-newParent");
			exit(1);
		}
		newParent->leaf = false;
		newParent->numKeys = 0;
		newParent->childNode[0] = root;
		*tree = newParent;//
#ifdef DEBUG_ATFER_SPLIT
	printf("before split\n");
//	printf("newParent: %x\n",newParent);
	for(int i=0;i<newParent->numKeys;i++){
		printf("%f,%s |%d| ",newParent->keys[i],newParent->dataStr[i],i);
	}
	printf("\n");
#endif

		BPTreeSplitChild(newParent,root,0);//newParent 是新的根节点，root是当前节点了

		BPTreeInsertNotFull(newParent,key,string);//往已经更新的根节点插入
	}
	else {
		BPTreeInsertNotFull(root,key,string);
	}
}
//把node的中间key给parent，以及分裂node
void BPTreeSplitChild(BPNode *parent,BPNode *node,int index)
{
	//在处理分裂出去的节点，新节点作为右节点
	BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
	if(!newNode){
		perror("BPTreeSplitLeaf-newNode");
		exit(1);
	}
	newNode->leaf = node->leaf;
	newNode->numKeys = ORDER - ORDER/2;//lowBound

	//把node的右半部分的key转移到newNode中
	for(int i = ORDER/2; i < ORDER; i++){
		newNode->keys[i-ORDER/2] = node->keys[i];
		strcpy(newNode->dataStr[i-ORDER/2],node->dataStr[i]);
		
		node->keys[i] = 0;
		strcpy(node->dataStr[i],"#");
	}
	//childNode
	if(!node->leaf){
		for(int i = ORDER/2;i < ORDER; i++){
			newNode->childNode[i-ORDER/2] = node->childNode[i];
			node->childNode[i] = NULL;
		}
	}
	//resize the temporay node
	node->numKeys = (ORDER/2);
	//父节点的孩子节点
	parent->childNode[index] = node;
	//parent->childNode[index+1] = newNode;
	//处理parent,先调整父节点后半段的位置
	for(int i = parent->numKeys; i > index; --i){
		parent->childNode[i+1] = parent->childNode[i];
	}
	parent->childNode[index+1] =  newNode;
	//parent->keys[index] = node->keys[ORDER/2];
	for(int i = (parent->numKeys - 1);i >= index; --i){
		parent->keys[i+1] = parent->keys[i];
	}
	parent->keys[index] = newNode->keys[0];//alway is first key of newNode!!!!
	++parent->numKeys;
	//把leaf node连接起来
	if(node->leaf){
		newNode->prevNode = node;
		newNode->nextNode = node->nextNode;
		node->nextNode = newNode;
		//node->prevNode = NULL;
		newNode->prevNode = node;
	}
}

void BPTreeInsertNotFull(BPNode *node,keyType key,char *string)
{
	//int i = node->numKeys;
	//case1 node is leaf
	if(node->leaf){
		int i = node->numKeys - 1;
		while((i >= 0) && (key < (node->keys[i]))){
		#ifdef DEBUG_INSERT
			printf("node %d,%f,%s\n",i,node->keys[i],node->dataStr[i]);
			printf("node %d,%f,%s\n",i,node->keys[i+1],node->dataStr[i+1]);
		#endif
			node->keys[i+1] = node->keys[i];
			strcpy(node->dataStr[i+1],node->dataStr[i]);//node->dataStr[i+1]=node->dataStr[i];
		#ifdef DEBUG_INSERT
			printf("node %d,%f,%s\n",i,node->keys[i],node->dataStr[i]);
			printf("node %d,%f,%s\n",i,node->keys[i],node->dataStr[i]);
		#endif
			--i;
		}
		node->keys[i+1] = key;
		strcpy(node->dataStr[i+1],string);
		++node->numKeys;
	}
	//case2 node is interl
	else{
		int i = node->numKeys - 1;
		while((i >= 0) && (key < node->keys[i])){
			--i;
		}
		++i;
		if(node->childNode[i]->numKeys >= ORDER){
			BPTreeSplitChild(node,node->childNode[i],i);
			if(key > node->keys[i]){
				++i;
			}
		}
		BPTreeInsertNotFull(node->childNode[i],key,string);
	}
}

















#ifdef DEBUG_ATFER_SPLIT
	printf("after split, insert\n");

//	printf("newParent: %x\n",newParent);
	for(int i=0;i<newParent->numKeys;i++){
		printf("%f,%s |%d| ",newParent->keys[i],newParent->dataStr[i],i);
	}
	printf("\n");

//	printf("newParent:childNode 0 %x\n",&newParent->childNode[0]);
	for(int i=0;i<newParent->childNode[0]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[0]->keys[i],newParent->childNode[0]->dataStr[i],i);
	}
	printf("\n");
//	printf("newParent:childNode 1 %x\n",&newParent->childNode[1]);
	for(int i=0;i<newParent->childNode[1]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[1]->keys[i],newParent->childNode[1]->dataStr[i],i);
	}
	printf("\n");
//	pause();
#endif
#ifdef DEBUG_ATFER_SPLIT
	printf("after insert\n");

//	printf("newParent: %x\n",newParent);
	for(int i=0;i<newParent->numKeys;i++){
		printf("%f,%s |%d| ",newParent->keys[i],newParent->dataStr[i],i);
	}
	printf("\n");

//	printf("newParent:childNode 0 %x\n",&newParent->childNode[0]);
	for(int i=0;i<newParent->childNode[0]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[0]->keys[i],newParent->childNode[0]->dataStr[i],i);
	}
	printf("\n");
//	printf("newParent:childNode 1 %x\n",&newParent->childNode[1]);
	for(int i=0;i<newParent->childNode[1]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[1]->keys[i],newParent->childNode[1]->dataStr[i],i);
	}
	printf("\n");
	pause();
#endif

